package com.chennan.algorithm.leetcode.eleven;

/**
 * @author chennan
 * @create 2021-11
 * 367. 有效的完全平方数
 * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
 *
 * 进阶：不要 使用任何内置的库函数，如  sqrt 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：num = 16
 * 输出：true
 * 示例 2：
 *
 * 输入：num = 14
 * 输出：false
 *
 */
public class IsPerfectSquare {
    public static void main(String[] args) {
        System.out.println(isPerfectSquare2(16));
    }

    public static boolean isPerfectSquare(int num) {
        if(num==1) return true;
        int middle = num/2;
        boolean flag = false;
        for (int i = 1; i <= middle; i++) {
            if(i*i>num){
                break;
            }
            if(i*i==num){
                flag=true;
                break;
            }
        }
        return flag;
    }

    /**
     * 二分法
     * @param num
     * @return
     */
    public static boolean isPerfectSquare2(int num) {
        if(num==1) return true;
        int left = 0;
        int right = num/2;

        boolean flag = false;
        while(left<=right){
            int middle = (left+right)/2+left;
            int ping =middle*middle;
            if(ping>num){
                right=middle-1;
            }
            if(ping<num){
                left=middle+1;
            }
            if(ping==num){
                flag=true;
                break;
            }
        }
        return flag;
    }

}
